class PriorityQueue {
    constructor(arr = []) {
        this.queue = arr
        this.init()
    }

    init() {
        let lastParentNodeIndex = Math.floor(this.queue.length / 2) - 1
        for (let i = lastParentNodeIndex; i >= 0; i--) {
            this.buildChildNodes(i)
        }
    }

    buildChildNodes(index) {
        let arr = this.queue
        let left = index * 2 + 1
        let right = index * 2 + 2
        let maxIndex = index
        let length = arr.length

        if (left < length && arr[left] > arr[maxIndex]) {
            maxIndex = left
        }

        if (right < length && arr[right] > arr[maxIndex]) {
            maxIndex = right
        }

        if (maxIndex !== index) {
            this.swap(index, maxIndex)
            this.buildChildNodes(maxIndex)
        }
    }

    peak() {
        return this.queue[0]
    }

    push(val) {
        this.queue.push(val)
        this.init()
    }

    pop() {
        let val = this.queue[0]
        this.queue[0] = this.queue.pop()
        this.init()
        return val
    }

    sort() {
        let res = []
        let length = this.queue.length
        for (let i = 0; i < length; i++) {
            res.push(this.pop())
        }
        this.queue = res
        return res
    }

    swap(index1, index2) {
        let arr = this.queue;
        [arr[index1], arr[index2]] = [arr[index2], arr[index1]]
    }
}